import java.lang.annotation.ElementType;
import java.time.Period;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-03
 * Time: 22:15
 */
public class Sort {
    /**
     * 希尔排序
     * @param array
     */
    public void shellSort(int []array){
        int gap=array.length;
        while(gap>=1){
            for (int i = gap; i < array.length; i++) {
                int temp=array[i];
                int j = i-gap;
                for (; j >=0 ; j-=gap) {
                    if(array[j]<=temp){
                        break;
                    }else{
                        //注意是j+gap不能是i,因为j在变化
                        array[j+gap]=array[j];
                    }
                }
                array[j+gap]=temp;
            }
            gap/=2;
        }
    }

    /**
     * 快速排序
     * 挖坑法
     */

    public void quickSort(int []array){
        quickSortFunc(array,0,array.length-1);
    }
    public void quickSortFunc(int []array,int left,int right){
        if(left>=right){
            return;
        }
        //小区间优化
        if((right-left+1)<=10){
            insertSortFunc(array,left,right);
        }else{
            int midIndex=getMid(array,left,right);
            swap(array,midIndex, left);
            int pivot=left;
            int temp=array[pivot];
            int begin=left;
            int end=right;
            while(begin<end){
                //                    必须有==不然死循环
                while(begin<end&&array[end]>=temp){
                    end--;
                }
                array[pivot]=array[end];
                pivot=end;
                while(begin<end&&array[begin]<=temp){
                    begin++;
                }
                array[pivot]=array[begin];
                pivot=begin;
            }
            array[begin]=temp;
            pivot=begin;
            quickSortFunc(array,left,pivot-1);
            quickSortFunc(array,pivot+1,right);
        }
    }
    /**
     * 三数取中
     */
    public int getMid(int []array,int left,int right){
        int mid=(left+right)>>>1;
        if(array[left]<array[mid]){
            if(array[mid]<array[right]){
                return mid;
            }else if(array[right]<array[left]){
                return left;
            }else{
                return right;
            }
        }else{
            if(array[left]<array[right]){
                return left;
            }else if(array[right]<array[mid]){
                return mid;
            }else{
                return right;
            }
        }
    }

    public static void swap2 (int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }


    public static void quickSort2(int[] arr) {
        int len = arr.length;
        partition(arr, 0, len-1);
    }


    /**
     *  快速排序左右指针
     */
    public static void partition(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int value = arr[left];
        int begin = left;
        int end = right;
        while (begin < end) {
            // 注意一定要带上 ==, 不然死循环
            while (begin < end && arr[end] >= value) {
                end--;
            }
            while (begin < end && arr[begin] <= value) {
                begin++;
            }
            swap2(arr, begin, end);
        }
        swap2(arr, left, begin);
        partition(arr, left, begin-1);
        partition(arr, begin+1, right);
    }


    /**
     *  快速排序前后指针
     */
    public static void partition2(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int value = arr[left];
        // 前后指针
        int end = left;
        int front = left + 1;
        while (front <= right) {
            if (arr[front] < value) {
                swap2(arr, end+1, front);
                end++;
            }
            front++;
        }
        swap2(arr, left, end);
        // 递归左边和右边
        partition2(arr, left, end-1);
        partition2(arr, end+1, right);
    }



    /**
     * 直接插入排序
     * @param array
     */

    public void insertSort(int []array){
        insertSortFunc(array,0,array.length-1);
    }

    public void insertSortFunc(int[] array,int left,int right){
        for (int end=left;end<right;end++) {
            int cur=end;
            int temp=array[end+1];
            while(cur>=left){
                if(array[cur]<=temp){
                    break;
                }else{
                    array[cur+1]=array[cur];
                    cur--;
                }
            }
            array[cur+1]=temp;
        }
    }

    /**
     * 堆排序
     * @param array
     */
    public void heapSort(int [] array){
        int end=array.length-1;
        //先建大堆
        creatBigHeap(array);
        //开始排序
        for (int i = end; i >0 ; i--) {
            swap(array,0,i);
            shiftDown(array,0,i-1);
        }
    }
    public void creatBigHeap(int []array){
        int end=array.length-1;
        //从最后一个非叶子节点开始调
        for (int i = (end-1)/2; i >=0 ; i--) {
            shiftDown(array,i,end);
        }
    }

    /**
     * 向下调整算法
     * @param array
     * @param parent
     * @param end
     */
    public void shiftDown(int []array,int parent,int end){
        int child=parent*2+1;
        if(child>end){
            //没有孩子直接返回
            return;
        }
        //至少有左孩子
        while(child<=end){
            if((child+1)<=end&&array[child+1]>array[child]){
                child++;
            }
            if(array[child]>array[parent]){
                //孩子大于双亲就交换
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

    /**
     * 归并排序
     * @param array
     */
    public void mergeSort(int[]array){
        mergeSortFunc(array,0,array.length-1);
    }

    public void mergeSortFunc(int []array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)>>>1;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        int begin1=left;
        int end1=mid;
        int begin2=mid+1;
        int end2=right;
        int[] temp=new int[right-left+1];
        int index=0;
        while(begin1<=end1&&begin2<=end2){
            if(array[begin1]<array[begin2]){
                temp[index++]=array[begin1++];
            }else{
                temp[index++]=array[begin2++];
            }
        }
        while(begin1<=end1){
            temp[index++]=array[begin1++];
        }
        while (begin2<=end2){
            temp[index++]=array[begin2++];
        }
        for (int i = 0; i < temp.length; i++) {
            array[i+left]=temp[i];
        }
    }

    /**
     * 快排非递归
     * @param array
     */
    public void quickSortNonR(int []array){
        quickSortNonRFunc(array,0,array.length-1);
    }


    public void quickSortNonRFunc(int[]array,int left,int right){
        if(left>=right){
            return;
        }
        Stack<Integer> stack=new Stack<>();
        stack.add(right);
        stack.add(left);
        while(!stack.isEmpty()){
            int begin=stack.pop();
            int end=stack.pop();
            //必须有不然数组越界
            if(begin>=end){
                continue;
            }
            int midIndex=getMid(array,begin,end);
            swap(array,begin,midIndex);
            int pivot=begin;
            int temp=array[pivot];
            int start=begin;
            int over=end;
            while(start<over){

                //必须over在前,start在后
                //这样才能保证over与start相遇位置之后都是大于temp的
                //才能把temp放在相遇位置
                while(start<over&&array[over]>=temp){
                    over--;
                }
                array[pivot]=array[over];
                pivot=over;

                while(start<over&&array[start]<=temp){
                    start++;
                }
                array[pivot]=array[start];
                pivot=start;
            }
            array[start]=temp;
            pivot=start;
            //右区间
            stack.add(end);
            stack.add(pivot+1);
            //左区间
            stack.add(pivot-1);
            stack.add(begin);
        }
    }

    /**
     * 归并排序非递归
     * @param array
     */
    public void mergerSortNonR(int[]array){
        mergerSortNonRFunc(array);
    }

    public void mergerSortNonRFunc(int[]array){
        for (int gap = 1; gap <array.length ; gap*=2) {
            //gap表示每组元素的个数
            for (int i = 0; i < array.length; i+=2*gap) {
                int begin1=i;
                int end1=begin1+gap-1;
                if(end1>=array.length){
                    end1=array.length-1;
                }
                int begin2=begin1+gap;
                int end2=begin1+2*gap-1;
                if(end2>=array.length){
                    end2=array.length-1;
                }
                int []temp=new int[end2-begin1+1];
                int index=0;
                while(begin1<=end1&&begin2<=end2){
                    if(array[begin1]<array[begin2]){
                        temp[index++]=array[begin1++];
                    }else{
                        temp[index++]=array[begin2++];
                    }
                }
                while(begin1<=end1){
                    temp[index++]=array[begin1++];
                }
                while (begin2<=end2){
                    temp[index++]=array[begin2++];
                }
                //注意begin1,end1,begin2,end2已经发生了变化,不能再用了
                for (int j = 0; j < temp.length; j++) {
                    array[i+j]=temp[j];
                }
            }
        }
    }
    public void swap(int []array,int index1,int index2){
        int temp=array[index1];
        array[index1]=array[index2];
        array[index2]=temp;
    }

    public void display(int []array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}
